"""
建立三张散列表。
edge 存储关系图；
costs 存储各个节点的开销（开销是指从起点到该节点的最小的权重）；
parents 存储各个节点的父节点是谁。
"""

import numpy as np


def find_lowest_cost_node(processed, costs):
    # float("inf")   表示正向无穷，一般我们对与节点到终点的位置距离定义为正向无穷
    lowest_cost = float("inf")
    lowest_cost_node = None
    size = len(costs)
    for node in range(size):  # 遍历所有的节点
        cost = costs[node]
        # 如果当前的节点开销更低而且没有被处理过，那么更新这个节点的开销
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


# 生成从start节点出发到其他节点的最短路径
def shortest_path(start=0, edges=None, costs=[]):
    if edges is None:
        edges = []
    size = len(edges)
    parents = [-1 for i in range(size)]  # 存上一个节点
    processed = []  # 存已经处理过的节点
    min_costs = [np.inf for i in range(size)]  # 从start到各节点最短距离
    # parents[start] = -1
    # processed.append(start)
    min_costs[start] = 0

    # 开始计算
    node = find_lowest_cost_node(processed, min_costs)  # 在未处理的节点中，找出开销最小的节点
    while node is not None:
        min_cost = min_costs[node]
        neighbors = [i for i in range(size) if edges[node][i]]
        for n in neighbors:
            new_cost = min_cost + costs[node][n]
            # 如果经历这个节点前往邻居更近，那么就更新邻居的开销，同时将邻居的父节点设为当前节点
            if min_costs[n] > new_cost:
                min_costs[n] = new_cost
                parents[n] = node
        # 将处理过的节点加入列表processed
        processed.append(node)
        # 找出下一个要处理的节点
        # print(costs)
        node = find_lowest_cost_node(processed, min_costs)
    return min_costs, parents
